package com.tgy.dynamic.programming;

/**
 * @Author: tgy
 * @Date: 2020/11/14 8:29 下午
 */
public class Knapsack01 {

    public int maxEqualValue(int[] weights, int[] values, int maxWeight) {


        int[] dp = new int[maxWeight + 1];

        for (int i = 1; i <= maxWeight; i++) {

            // 这里唯独i=0没有赋值为无穷小，是为后面凑整做准备
            dp[i] = Integer.MIN_VALUE;
        }

        for (int i = 1; i <= weights.length; i++) {

            for (int j = maxWeight; j >= weights[i - 1]; j--) {

                dp[j] = Math.max(dp[j], values[i - 1]+ dp[j-weights[i  - 1]]);
            }
        }

        return dp[maxWeight] > 0 ? dp[maxWeight]: -1;
    }

    /**
     * 一维数组
     * @param weights
     * @param values
     * @param maxWeight
     * @return
     */
//    public int maxValue(int[] weights, int[] values, int maxWeight) {
//
//        int[] dp = new int[maxWeight + 1];
//
//        for (int i = 1; i <= weights.length; i++) {
//
//            for (int j = maxWeight; j >= weights[i-1] ; j--) {
//
//                dp[j] = Math.max(dp[j], values[i - 1] + dp[j - weights[i - 1]]);
//            }
//        }
//
//        return dp[maxWeight];
//    }
    /**
     * 二维数组实现
     * @param weights
     * @param values
     * @param maxWeight
     * @return
     */
    public int maxValue(int[] weights, int[] values, int maxWeight) {

        if (weights.length == 0 || values.length == 0 || maxWeight <= 0) {

            return 0;
        }

        if (weights.length != values.length) {

            return 0;
        }

        /**
         *  dp[i][j] 代表放入了i个物品，最大承重为j的最大价值 dp[i][j]
         *  dp[0][j] = 0;
         *  dp[i][0] = 0;
         */
        int[][]dp = new int[values.length + 1][maxWeight + 1];

        for (int i = 1; i <= values.length; i++) {

            for (int j = 1; j <= maxWeight; j++) {

                if (weights[i - 1] <= j) {// 可以选择第i个物品


                    // 从不加第i个物品和加了第i个物品中间获取最大值
                    dp[i][j] = Math.max(dp[i-1][j], values[i - 1] + dp[i - 1][j - weights[i - 1]]);
                }else {

                    // 不可以选择第i个物品，
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }



        return dp[values.length][maxWeight];
    }
}
